package ljl.codetop;

import java.util.HashSet;
import java.util.Set;

/**
 */
public class _3_length_of_longest_substring {

    /**
     * 看名就知道是滑动窗口，这个不可能难道我除非我突发脑梗
     *
     * 确实蒙出来了，不过花了挺长时间，将近二十多分钟不到
     */
    static class tryout {

        /*
        每次来一个字符，加入进去，这可能会导致新加入的这个字符数量 >1，所以左边得缩
        前提是：len > 1 而且最右边那个字符个数大于 1，如果 == 1 就不用缩了
        缩完以后得和结果进行比较。
         */
        public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) return 0;
            int[] chars = new int[128];
            int from = 0, len = 0;
            int resLen = 1;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                chars[c]++;
                len++;
                while (len > 1 && chars[c] > 1) {
                    chars[s.charAt(from)]--;
                    from++;
                    len--;
                }
                if (len > resLen) {
                    resLen = len;
                }
            }
            return resLen;
        }
    }

    /**
     * 他这个是枚举起始位置，非常的反直觉，对我来说
     */
    static class off1 {
        public int lengthOfLongestSubstring(String s) {
            boolean[] chars = new boolean[128];
            int n = s.length();
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    chars[s.charAt(i - 1)] = false;
                }
                // 删除前一个字符，可能会导致之前进不去 set 的字符进去，所以 rk 可能会增加
                // 比如 abac，到 b 了，在 a 的时候集合里是 ab，到 b 时，集合时只有 b，可以 b a c，三个字符进去，很不错
                while (rk + 1 < n && !chars[s.charAt(rk + 1)]) {
                    chars[s.charAt(rk + 1)] = true;
                    ++rk;
                }
                if (rk == n)
                    break;
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    }

    static class copy_off1 {
        public int lengthOfLongestSubstring(String s) {
            boolean[] chars = new boolean[128];
            int rk = -1, res = 1;
            for (int i = 0; i < s.length(); i++) {
                if (i > 0)
                    chars[s.charAt(i - 1)] = false;
                while (rk < s.length() - 1 && !chars[s.charAt(rk + 1)])
                    chars[s.charAt(rk++ + 1)] = true;
                res = Math.max(res, rk - i + 1);
            }
            return res;
        }
    }
}
